package tree;


import java.util.LinkedList;
import java.util.Queue;

public class 找树左下角的值_513 {
    public int findBottomLeftValue_bfs(TreeNode root) {
        // bfs
        int val = root.val;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            int size = queue.size();
            for(int i = 0; i< size; i++) { // 双层循环的方式  大循环while中有个每层循环
                TreeNode node = queue.poll();
                if(i == 0) val = node.val; // 每层第一个就是最左侧那个
                if(node.left != null) queue.offer(node.left);
                if(node.right != null) queue.offer(node.right);
            }
        }
        return val;
    }



    // 以下为dfs解法
    private int depth = 0;
    private int bottomLeft = 0;

    public int findBottomLeftValue_dfs(TreeNode root) {
        dfs(root, 1);  // 先序遍历 中左右   层数第一次变化的肯定是最左边的
        return bottomLeft;
    }

    private void dfs(TreeNode node, int depth) {
        if(node.left == null && node.right == null && depth > this.depth) {
            this.depth = depth;
            bottomLeft = node.val;
        }

        if(node.left != null) {
            dfs(node.left, depth + 1);
        }
        if(node.right != null) {
            dfs(node.right, depth + 1);
        }
    }
}

class TreeNode {
     int val;
     TreeNode left;
     TreeNode right;
     TreeNode() {}
     TreeNode(int val) { this.val = val; }
     TreeNode(int val, TreeNode left, TreeNode right) {
         this.val = val;
         this.left = left;
         this.right = right;
     }
 }
